Integer to english words

Time: O(LogN); Space: O(1); hard

Note:

  • N is the value of the integer

Convert a non-negative integer to its english words representation.

Given input is guaranteed to be less than 2^31 - 1.

Example 1:

Input: num = 123

Output: “One Hundred Twenty Three”

Example 2:

Input: num = 12345

Output: “Twelve Thousand Three Hundred Forty Five”

Example 3:

Input: num = 1234567

Output: “One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven”

Hints:

  1. Did you see a pattern in dividing the number into chunk of words? For example, 123 and 123000.

  2. Group the number by thousands (3 digits). You can write a helper function that takes a number less than 1000 and convert just that chunk to words.

  3. There are many edge cases. What are some good test cases? Does your code work with input such as 0? Or 1000010? (middle chunk is zero and should not be printed out)

[1]:

class Solution1(object):
    def numberToWords(self, num):
        """
        :type num: int
        :rtype: str
        """
        if num == 0:
            return "Zero"

        lookup = {0: "Zero", 1:"One", 2: "Two", 3: "Three", 4: "Four", \
                  5: "Five", 6: "Six", 7: "Seven", 8: "Eight", 9: "Nine", \
                  10: "Ten", 11: "Eleven", 12: "Twelve", 13: "Thirteen", 14: "Fourteen", \
                  15: "Fifteen", 16: "Sixteen", 17: "Seventeen", 18: "Eighteen", 19: "Nineteen", \
                  20: "Twenty", 30: "Thirty", 40: "Forty", 50: "Fifty", 60: "Sixty", \
                  70: "Seventy", 80: "Eighty", 90: "Ninety"}

        unit = ["", "Thousand", "Million", "Billion"]

        res, i = [], 0
        while num:
            cur = num % 1000
            if num % 1000:
                res.append(self.threeDigits(cur, lookup, unit[i]))
            num //= 1000
            i += 1
        return " ".join(res[::-1])

    def threeDigits(self, num, lookup, unit):
        res = []
        if num // 100:
            res = [lookup[num // 100] + " " + "Hundred"]
        if num % 100:
            res.append(self.twoDigits(num % 100, lookup))
        if unit != "":
            res.append(unit)
        return " ".join(res)

    def twoDigits(self, num, lookup):
        if num in lookup:
            return lookup[num]
        return lookup[(num // 10) * 10] + " " + lookup[num % 10]

[2]:

s = Solution1()
num = 123
assert s.numberToWords(num) == "One Hundred Twenty Three"
num = 12345
assert s.numberToWords(num) == "Twelve Thousand Three Hundred Forty Five"
num = 1234567
assert s.numberToWords(num) == "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"